package LearnDataStructure.d_图结构.例题;

import java.sql.Array;
import java.util.*;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-16 18:18
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.d_图结构.例题
 */
/*
问题描述
 　　栋栋居住在一个繁华的C市中，然而，这个城市的道路大都年久失修。
    市长准备重新修一些路以方便市民，于是找到了栋栋，希望栋栋能帮助他。
 　　C市中有n个比较重要的地点，市长希望这些地点重点被考虑。现在可以修一些道路来连接其中的一些地点，每条道路可以连接其中的两个地点。
    另外由于C市有一条河从中穿过，也可以在其中的一些地点建设码头，所有建了码头的地点可以通过河道连接。
 　　栋栋拿到了允许建设的道路的信息，包括每条可以建设的道路的花费，以及哪些地点可以建设码头和建设码头的花费。
 　　市长希望栋栋给出一个方案，使得任意两个地点能只通过新修的路或者河道互达，同时花费尽量小。

输入格式
 　　输入的第一行包含两个整数n, m，
    分别表示C市中重要地点的个数和可以建设的道路条数。
    所有地点从1到n依次编号。
 　　接下来m行，每行三个整数a, b, c，
    表示可以建设一条从地点a到地点b的道路，花费为c。

    若c为正，表示建设是花钱的，
    如果c为负，则表示建设了道路后还可以赚钱（比如建设收费道路）。
 　　接下来一行，包含n个整数w_1, w_2, …, w_n。
    如果w_i为正数，则表示在地点i建设码头的花费，
    如果w_i为-1，则表示地点i无法建设码头。
 　　输入保证至少存在一个方法使得任意两个地点能只通过新修的路或者河道互达。

输出格式
 　　输出一行，包含一个整数，
    表示使得所有地点通过新修道路或者码头连接的最小花费。
    如果满足条件的情况下还能赚钱，那么你应该输出一个负数。

样例输入
5 5
1 2 4
1 3 -1
2 3 3
2 4 5
4 5 10
-1 10 10 1 1

样例输出
9

样例说明
 　　建设第2、3、4条道路，在地点4、5建设码头，总的花费为9。

数据规模和约定
 　　对于20%的数据，1<=n<=10，1<=m<=20，0<=c<=20，w_i<=20；
 　　对于50%的数据，1<=n<=100，1<=m<=1000，-50<=c<=50，w_i<=50；
 　　对于70%的数据，1<=n<=1000；
 　　对于100%的数据，1 <= n <= 10000，1 <= m <= 100000，-1000<=c<=1000，-1<=w_i<=1000，w_i≠0。

 */
public class b_城市建设byKruskal {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int pointNum = scanner.nextInt();
        int edgeNum = scanner.nextInt();
        int portNum = 0;
        List<GraphNode_EdgeSet<Integer>> edgeList = new ArrayList<GraphNode_EdgeSet<Integer>>();
        for (int i = 0; i < edgeNum; i++) {
            edgeList.add(new GraphNode_EdgeSet<Integer>(scanner.nextInt(),scanner.nextInt(),scanner.nextInt()));//存普通的边
        }
        for (int i = 0; i < pointNum; i++) {//把码头抽象成一个点0，0可以和若干个普通点建立道路前提是portCost!=-1
            int portCost = scanner.nextInt();
            if (portCost < 0) {
                continue;
            }
            edgeList.add(new GraphNode_EdgeSet<Integer>(i+1,0,portCost));//存于码头有关的边
            portNum++;
        }
        /*
        把问题抽象成普通点加上一个点0
        这些点组成的图A
        求A的最小生成树
         */
        f_Kruskal贪心 helper = new f_Kruskal贪心(edgeList,pointNum + 1);
        helper.buildMST();
        /*
        我画一下例子数据的图
              ---------------
              |             |
        1 --- 2 --- 4 ----- 0-----
        |     |     |       |    |
        ----- 3     5 -------    |
              |                  |
              --------------------
         */
        int totalCost = 0;
        Set<GraphNode_EdgeSet<Integer>> treeEdgeList = helper.getTreeEdgeList();
        for (GraphNode_EdgeSet<Integer> element : treeEdgeList) {
            totalCost += element.distance;
            System.out.println(element.toString());
        }
        System.out.println("总成本是：" + totalCost);
    }



    static class f_Kruskal贪心 {
        //源数据，边集
        public List<GraphNode_EdgeSet<Integer>> edgeList = null;
        //结果，最小生成树的边集
        public Set<GraphNode_EdgeSet<Integer>> treeEdgeList = new HashSet<GraphNode_EdgeSet<Integer>>();
        //帮助map，保存每个边中的“每个点”与“并查集节点”的映射
        public Map<Integer, UnionFindNode> pointAndNode = new HashMap<Integer, UnionFindNode>();
        //总顶点个数
        public int N = 0;

        public int weight = 0;
        public UnionFindSet helper = new UnionFindSet();

        public f_Kruskal贪心(List<GraphNode_EdgeSet<Integer>> edgeList, int N) {
            this.edgeList = edgeList;
            this.N = N;
            //为每条边的每个点，与一个并查集的点，建立映射
            for (GraphNode_EdgeSet<Integer> edge : edgeList) {
                pointAndNode.put(edge.start, new UnionFindNode());
                pointAndNode.put(edge.end, new UnionFindNode());
            }
        }

        public Set<GraphNode_EdgeSet<Integer>> getTreeEdgeList() {
            return treeEdgeList;
        }

        public int getWeight() {
            return weight;
        }

        /**
         * 构建最小生成树
         * Kruskal核心语句
         */
        public void buildMST() {
            //先按权值从小到大排序
            Collections.sort(edgeList);
            //迭代，判断每一条边是否可以添加进树边集中
            for (GraphNode_EdgeSet<Integer> edge : edgeList) {
                if (!check(edge)) {
                    continue;
                }
                treeEdgeList.add(edge);
                weight = weight + edge.distance;
                if (treeEdgeList.size() == N - 1) {///满足了，就不需要继续迭代了
                /*
                根据树的定义
                如果边的数量 == 顶点的数量 - 1
                那么就是树，否则就不构成树
                 */
                    return;
                }
            }
        }

        /**
         * 检查这条边的两个点是否都被使用过
         * 如果都没有使用
         * 如果只是用了一个点
         * 就true，同时把这两个点都合并。也就是打上“使用了”的标记
         * @param edge
         * @return
         */
        private boolean check(GraphNode_EdgeSet<Integer> edge) {
            UnionFindNode nodeStart = pointAndNode.get(edge.start);
            UnionFindNode nodeEnd = pointAndNode.get(edge.end);
            if (helper.find(nodeStart) != helper.find(nodeEnd)) {
                helper.union(nodeStart,nodeEnd);
                return true;
            }
            return false;
        }
    }

    static class UnionFindNode{
        public UnionFindNode parent;
    }

    static class UnionFindSet {

        public UnionFindNode find(UnionFindNode source) {
            UnionFindNode node = source;
            HashSet<UnionFindNode> path = new HashSet<UnionFindNode>();
            while (node.parent != null) {//顺着当前节点的父节点，一路找到root
                path.add(node);
                node = node.parent;
            }
            //跳出while后，node就是root
            //下面是重新认父，也就是减小树的高度
            for (UnionFindNode element : path) {//将循环中路过的所有的节点，的父亲，全部改成root
                element.parent = node;
            }
            return node;//root
        }


        public void union(UnionFindNode parent, UnionFindNode child) {
            find(child).parent = parent;
        /*
        find(child)的结果是返回当前并查集的root
        root的parent是null
        把parent当成了root的父节点
        所以说parent成为了新的root
         */
        }
    }

    static class GraphNode_EdgeSet<T> implements Comparable<GraphNode_EdgeSet<T>> {
        public T start = null;
        public T end = null;
        public int distance = 0;

        public GraphNode_EdgeSet(T start, T end, int distance) {
            this.start = start;
            this.end = end;
            this.distance = distance;
        }

        /**
         * 按权值从小到大排序
         * @param other
         * @return
         */
        @Override
        public int compareTo(GraphNode_EdgeSet<T> other) {
            int otherDistance = other.distance;
            int result = 0;
            if (this.distance > otherDistance) {
                result = 1;
            } else if (this.distance < otherDistance) {
                result = -1;
            }
            return result;
        }

        @Override
        public String toString() {
            return start + " -> " + end + " : " + distance;
        }
    }
}
